package 力扣算法练习.main1.newPart1;

public class day14 {
    //https://www.nowcoder.com/practice/fbcf95ed620f42a88be24eb2cd57ec54?tpId=167&tqId=34050&ru=/exam/oj
    public int getValue(int[] gifts, int n) {
        if (gifts.length == 1) return 0;
        //将数组排序,两两抵消,当最后剩下的一个和排序后的中间元素相等时就是
        int slow = 0, fast = 1;
        int count = 1;
        while (fast != gifts.length && slow != gifts.length) {
            //两个数不同就相互抵消,相同就自增1
            if (gifts[slow] == gifts[fast]) {
                count++;
                fast++;
            } else {
                if (count > 0) {
                    slow++;
                    count--;
                    fast++;
                } else {
                    slow = ++fast;
                    fast++;
                }
            }
        }
        if (count > 0 && gifts[slow] == gifts[(n / 2) + 1]) {
            return gifts[slow];
        }
        return 0;
    }

}
